11846 - Finding Seats Again/11846.3.cpp

   1 // Accepted - Little tricks to try to make it faster. Doesn't really work.
   2 using namespace std;
   3 #include <algorithm>
   4 #include <iostream>
   5 #include <iterator>
   6 #include <numeric>
   7 #include <sstream>
   8 #include <fstream>
   9 #include <cassert>
  10 #include <climits>
  11 #include <cstdlib>
  12 #include <cstring>
  13 #include <string>
  14 #include <cstdio>
  15 #include <vector>
  16 #include <cmath>
  17 #include <queue>
  18 #include <deque>
  19 #include <stack>
  20 #include <list>
  21 #include <map>
  22 #include <set>
  23
  24 #define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
  25 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  26 #define D(x) cout << #x " is " << x << endl
  27
  28 namespace IO {
  29 #define MAXBUFF (1<<18)
  30    char inBuffer[MAXBUFF], *pIn = inBuffer+MAXBUFF;
  31    char outBuffer[MAXBUFF], *pOut = outBuffer;
  32
  33    inline char read_char() {
  34       if( pIn == inBuffer+MAXBUFF ) {
  35          fread( inBuffer, 1, MAXBUFF, stdin );
  36          pIn = inBuffer;
  37       }
  38       return *pIn++;
  39    }
  40
  41    inline int read_int() {
  42       char c;
  43       while( !isdigit(c = read_char()) );
  44       int ret = c - '0';
  45       while( isdigit(c = read_char()) ) ret = (ret << 3) + (ret << 1) + c - '0';
  46       return ret;
  47    }
  48
  49    void flush() {
  50       fwrite( outBuffer, 1, pOut-outBuffer, stdout );
  51       pOut = outBuffer;
  52    }
  53
  54    inline void write( char c ) {
  55       if( pOut == outBuffer+MAXBUFF ) {
  56          fwrite( outBuffer, 1, MAXBUFF, stdout );
  57          pOut = outBuffer;
  58       }
  59       *pOut++ = c;
  60    }
  61 }
  62
  63 const int MAXN = 20;
  64 const int MAXK = 26;
  65
  66 int N, K;
  67 char mat[MAXN+1][MAXN+1];
  68
  69 short r1[MAXK * 32], r2[MAXK * 32], c1[MAXK * 32], c2[MAXK * 32];
  70
  71 vector<int> regionsAt[MAXN+1][MAXN+1];
  72
  73 int totalRegions;
  74
  75 inline void fillRegion(int r, char letter) {
  76     for (int i = r1[r]; i <= r2[r]; ++i) {
  77         for (int j = c1[r]; j <= c2[r]; ++j) {
  78             mat[i][j] = letter;
  79         }
  80     }
  81 }
  82
  83 inline bool isEmpty(int r) {
  84     for (int i = r1[r]; i <= r2[r]; ++i) {
  85         for (int j = c1[r]; j <= c2[r]; ++j) {
  86             if (mat[i][j] != '.') return false;
  87         }
  88     }
  89     return true;
  90 }
  91
  92 bool backtrack(int cell, char face) {
  93     int cr = cell / N;
  94     int cc = cell % N;
  95
  96     if (cr >= N or cc >= N) {
  97         for (int i = 0; i < N; ++i) {
  98             for (int j = 0; j < N; ++j) {
  99                 IO::write(mat[i][j]);
 100             }
 101             IO::write('\n');
 102         }
 103         return true;
 104     }
 105
 106     if (mat[cr][cc] != '.') return backtrack(cell + 1, face);
 107
 108     for (int k = 0, m = regionsAt[cr][cc].size(); k < m; ++k) {
 109         int r = regionsAt[cr][cc][k];
 110         if (!isEmpty(r)) continue;
 111         fillRegion(r, face);
 112         if (backtrack(cell + 1, face + 1)) return true;
 113         fillRegion(r, '.');
 114     }
 115     return false;
 116 }
 117
 118 int main(){
 119     while (true) {
 120         N = IO::read_int();
 121         K = IO::read_int();
 122         if (N == 0 and K == 0) break;
 123
 124         for (int i = 0; i < N; ++i) {
 125             for (int j = 0; j < N; ++j) {
 126                 char c = IO::read_char(); while (isspace(c)) c = IO::read_char();
 127                 mat[i][j] = c;
 128                 regionsAt[i][j].clear();
 129             }
 130         }
 131
 132         totalRegions = 0;
 133
 134         for (int i = 0; i < N; ++i) {
 135             for (int j = 0; j < N; ++j) {
 136                 if (mat[i][j] == '.') continue;
 137                 int size = mat[i][j] - '0';
 138                 mat[i][j] = '.';
 139                 for (int width = 1; width <= size; ++width) {
 140                     if (size % width != 0) continue;
 141                     int height = size / width;
 142                     for (int ii = max(0, i - height + 1); ii + height - 1 < N and ii <= i; ++ii) {
 143                         for (int jj = max(0, j - width + 1); jj + width - 1 < N and jj <= j; ++jj) {
 144                             r1[totalRegions] = ii;
 145                             r2[totalRegions] = ii + height - 1;
 146                             c1[totalRegions] = jj;
 147                             c2[totalRegions] = jj + width - 1;
 148                             if (isEmpty(totalRegions)) {
 149                                 regionsAt[ii][jj].push_back( totalRegions );
 150                                 totalRegions++;
 151                             }
 152                         }
 153                     }
 154                 }
 155                 mat[i][j] = '0' + size;
 156             }
 157         }
 158
 159         for (int i = 0; i < N; ++i) {
 160             for (int j = 0; j < N; ++j) {
 161                 mat[i][j] = '.';
 162             }
 163         }
 164         backtrack(0, 'A');
 165     }
 166     IO::flush();
 167     return 0;
 168 }